package cn.z2huo.algorithm.sort.insert.straight;

import java.util.Arrays;

/**
 * <p>直接插入排序，时间复杂度为 O(n^2)，比简单选择排序和冒泡排序快很多
 *
 * @author z2huo
 */
public class StraightInsertSorting {

    public int[] sort(int[] array) {
        if (array == null || array.length == 0) {
            return new int[0];
        }
        // 此循环每一次遍历前，索引位置小于 i 的子序列都是正序的
        // 循环遍历是为了寻找 i 位置的元素在有序子序列中正确的位置
        for (int i = 1; i < array.length; i++) {
            int element = array[i];
            int j = i - 1;
            // 当 i 位置的元素小于 j 位置的元素时
            // 将 j 位置的元素向右移动一位
            // 之后 j 会递减，也就是继续判断再左一位的元素与 i 位置元素的大小，满足条件时继续向右移动
            // 直到 j < 0 或者 j 位置的元素大于 i 位置的元素时，跳出循环
            for (; j >= 0 && element < array[j]; j--) {
                array[j + 1] = array[j];
            }
            // 跳出循环前会执行 j--，所以 i 位置元素最终所处的位置为 j + 1
            array[j + 1] = element;
        }
        return array;
    }

    /**
     * <p>附带移动次数和比较次数
     *
     * @param array 待排序数组
     * @return 已排序数据
     */
    @Deprecated
    public int[] sort2(int[] array) {
        if (array == null) {
            return null;
        }
        int moveTimes = 0;
        int compareTimes = 0;
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            // 将比 array[i] 大的元素向右移
            while (j >= 0 && array[j] > temp) {
                array[j + 1] = array[j];
                j--;
                moveTimes++;
                compareTimes++;
            }
            // 找到 array[i] 元素该插入的位置，存取该元素
            array[j + 1] = temp;
        }

        System.out.println(Arrays.toString(array));
        System.out.println("移动次数：" + moveTimes);
        System.out.println("比较次数：" + compareTimes);
        return array;
    }

}
